package vj.bfs;

import vj.graph.Graph;
import vj.graph.Graph.AdjList;

import java.util.LinkedList;

public class BFSUtils {
  
  public static int shortestPath(Graph G, int s, int dest) {
    boolean visited[] = new boolean[G.V() + 1];
    int d[] = new int[G.V() + 1];
    for(int i = 1; i < d.length; i++) {
      d[i] = Integer.MAX_VALUE;
    }
    visited[s] = true;
    d[s] = 0;
    LinkedList<Integer> q = new LinkedList<Integer>();
    q.add(s);
    while(!q.isEmpty()) {
      int u = q.remove();
      AdjList list = G.getAdjList(s);
      int v;
      while(list.hasNext()) {
        v = list.next();
        if(!visited[v]) {
          q.add(v);
          visited[v] = true;
          d[v] = d[u] + 1;
        }
      }
    }
    return d[dest];
  }
	
	/*
	 * Vertices are represented as integers from 1..N
	 * AdjList is the list of neighbors
	 */
	public static void cycleDetect(Graph G, int s) {
		boolean visited[] = new boolean[G.V() + 1];
		LinkedList<Integer> q = new LinkedList<Integer>();
		q.push(s);
		visited[s] = true;
		while(!q.isEmpty()) {
			int u = q.pop();
			AdjList list = G.getAdjList(s);
			int v;
			while(list.hasNext()) {
				v = list.next();
				if(!visited[v]) {
					q.push(v);
					visited[v] = true;
				} else {
					System.out.println("Cycle detected at vertex "+ v );
					break;
				}
			}
		}
	}
	
	public static void BFS(Graph G, int start) {
		boolean visited[] = new boolean[G.V() + 1];
		//boolean discovered[] = new boolean[G.V() + 1];
		//boolean processed[] = new boolean[G.V() + 1];
		int parent[] = new int [G.V() + 1];
		LinkedList<Integer> q = new LinkedList<Integer>();
		q.add(start);
		visited[start] = true;
		
		while(!q.isEmpty()) {
			int current, y;
			current = q.remove();
			processVertexEarly(current);
			//processed[current] = true;
			AdjList iterator = G.getAdjList(current);
			while(iterator.hasNext()) {
				y = iterator.next();
				//processEdge(current, y);
				if(visited[y] == false) {
					q.add(y);
					visited[y] = true;
					parent[y] = current;
				}
			}
			//processVertexLate(current);
		}
	}

	/**
	 * If there is a disconnected veretex also, this method will visit it. 
	 * 
	 * @param G
	 * @param start
	 */
	public static void BFSFull(Graph G, int start) {
		boolean visited[] = new boolean[G.V() + 1];
		//boolean discovered[] = new boolean[G.V() + 1];
		//boolean processed[] = new boolean[G.V() + 1];
		int parent[] = new int [G.V() + 1];
		LinkedList<Integer> q = new LinkedList<Integer>();
		int current;
		int y;
		// for all vertices in V
		q.add(start);
		visited[start] = true;
		for(int i = 1; i <= G.V(); i++) {
			if(!visited[i])
				q.add(i);
			while(!q.isEmpty()) {
				current = q.remove();
				processVertexEarly(current);
				//processed[current] = true;
				AdjList iterator = G.getAdjList(current);
				while(iterator.hasNext()) {
					y = iterator.next();
					//processEdge(current, y);
					if(visited[y] == false) {
						q.add(y);
						visited[y] = true;
						parent[y] = current;
					}
				}
				//processVertexLate(current);
			}
		}
	}

	
	
	public static void BFS1(Graph G, int start) {
		boolean discovered[] = new boolean[G.V() + 1];
		boolean processed[] = new boolean[G.V() + 1];
		int parent[] = new int [G.V() + 1];
		LinkedList<Integer> q = new LinkedList<Integer>();
		q.add(start);
		discovered[start] = true;
		
		while(!q.isEmpty()) {
			int current, y;
			current = q.remove();
			processVertexEarly(current);
			processed[current] = true;
			AdjList iterator = G.getAdjList(current);
			while(iterator.hasNext()) {
				y = iterator.next();
				if(processed[y] == false || G.directed())
					processEdge(current, y);
				if(discovered[y] == false) {
					q.add(y);
					discovered[y] = true;
					parent[y] = current;
				}
			}
			//processVertexLate(current);
		}
	}
	
	// BFS gives the shortest path	only if the graph is unweighted
	public static void find_path(int start, int end, int parents[]) {
		if ((start == end) || (end == -1))
			System.out.println("\n" + start);
		else {
			find_path(start, parents[end], parents);
			System.out.println(" " + end);
		}
	}

	private static void processVertexEarly(int current) {
		System.out.println("Processing vertex "+ current /*+ " early."*/);
		
	}
	private static void processEdge(int v, int y) {
		System.out.println("Processing edge "+v+ " -> "+ y + "\n");
		
	}
	private static void processVertexLate(int current) {
		System.out.println("Processing vertex "+current+ " late.");
		
	}
	
	
	///////////////////// ALL BIPARTITE RELATED METHODS /////////////////////////////////////
	
	public static boolean isBipartite(Graph G) {
		int i;
		boolean bipartite = true;
		boolean discovered[] = new boolean[G.V() + 1];
		boolean processed[] = new boolean[G.V() + 1];
		int color[] = new int[G.V() + 1]; 
		LinkedList<Integer> q = new LinkedList<Integer>();
		int v, y;
		// 0 - Uncoloured 1= Black 2 = White
		for(i = 1; i <= G.V(); i++ ) 
			color[i] = 0;
		
		for(i = 1; i<= G.V(); i++) {
			if(discovered[i] == false) {
				color[i] = 2;
				//BFS2(G, i, color);
				discovered[i] = true;
				q.add(i);
				while(!q.isEmpty()) {
					v = q.remove();
					//processVertexEarly(current);
					processed[v] = true;
					AdjList iterator = G.getAdjList(v);
					while(iterator.hasNext()) {
						y = iterator.next();
						if(processed[y] == false || G.directed())
							processEdge2(v, y, color);
						if(discovered[y] == false) {
							q.add(y);
							discovered[y] = true;
							//parent[y] = current;
						}
					}
				}
			}
		}
		return bipartite;
	}


	private static void processEdge2(int x, int y, int color[]) {
		if (color[x] == color[y]) {
			System.out.println("Warning: not bipartite due to " + x + "," + y+ "\n");
		} else {
			int color1 = complement(color[x]);
			System.out.println("Coloring vertex "+ y +" with "+ color1);
			color[y] = color1;
		}
	}

	private static int complement(int color) {
		if (color == 2)
			return 1;
		if (color == 1)
			return 2;
		return 0;
	}
	
///////////////////// END OF BIPARTITE RELATED METHODS /////////////////////////////////////
	
	

}
